Image collation according to a local feature amount is a technique of calculating a local feature amount from a large number of feature points extracted from two input images and comparing a feature point of a first image with a feature point of a second image to determine whether or not a degree of similarity of the local feature amount is high. An objective such as same image searching, similar image searching, and image recognition can be realized by image collation. Hereinafter, a pair of a first image and a second image obtained by imaging an object different from an object appearing in the first image is referred to as unrelated images. A pair of a first image and a second image obtained by imaging the same object as an object appearing in the first image is referred to as related images. In the related technology, for two unrelated images, when both of the images include a repetitive pattern such as a checkered pattern, a fine pattern of texture, or the like, there may be a large number of feature points which are incorrectly matched between the images. Accordingly, an unrelated image is often erroneously recognized as a related image.
In order to reduce an influence of this problem, an image collation device that considers the consistency of a spatial relationship, a geometric transformation, or the like has been invented. A spatial relationship is a proximity relationship or a relative positional relationship between feature points. Hereinafter, a pair of feature points having a high degree of similarity for a local feature amount between two images is referred to as tentative matching points. A geometric transformation means linear transformation parameters, a displacement vector, or the like calculated from geometric characteristics of two feature points constituting the tentative matching points. Hereinafter, a tentative matching point satisfying limiting conditions such as a spatial relationship or geometric transformation among the tentative matching points is called a correct matching points.
The image collation devices disclosed in Non-Patent Document 1 and 2 include a process of searching for neighbors in a position coordinate space of a feature point in an input image, a process of calculating a relative position vector from a pair of feature points that are neighbors, a process of quantizing the relative position vector, a process of quantizing a local feature amount of the feature point, a process of creating an inverted index on the basis of a result of the quantization, a process of identifying a pair of correct matching points using the inverted index, and a process of calculating a degree of similarity between images on the basis of a pair of correct matching points. The image collation device disclosed in Non-Patent Document 3 includes a process of calculating geometric transformation parameters indicating scaling, rotation, and displacement from a tentative matching point between input images, a process of quantizing the geometric transformation parameters, a process of creating a voting histogram on the basis of a result of the quantization, and a process of calculating a degree of similarity between images on the basis of the voting histogram.